package index;


import heap.RID;

import java.io.*;

import exceptions.IndexFullDeleteException;
import exceptions.RedistributeException;

import Transaction.Transaction;

import storage.data.Page;
import storage.data.PageID;

public class IndexPage extends BTPage {
	public IndexPage(PageID pageno, int keyType,Transaction tx,String table) throws Exception {
		super(pageno, keyType);
		setType(NodeType.INDEX,tx,table,pageno);
	}

	public IndexPage(Page page, int keyType,Transaction tx,String table) throws Exception {
		super(page, keyType);
		setType(NodeType.INDEX,tx,table,curPage);
	}

	public IndexPage(int keyType,Transaction tx,String table) throws Exception {
		super(keyType,tx,table);
		setType(NodeType.INDEX,tx,table,curPage);
	}

	/**
	 * inserts a <key, pageNo> value into the index page
	 * 
	 * @param key
	 * @param pageNo
	 * @return
	 * @throws Exception
	 */
	public RID insertKey(KeyClass key, PageID pageNo,Transaction tx,String table) throws Exception {
		RID rid;
		KeyDataEntry entry;
		entry = new KeyDataEntry(key, pageNo);
		rid = super.insertRecord(entry,tx,table);
		return rid;
	}

	/**
	 * OPTIONAL: fullDeletekey This is optional, and is only needed if you want
	 * to do full deletion. Return its RID. delete key may != key. But delete
	 * key <= key, and the delete key is the first biggest key such that delete
	 * key <= key
	 * 
	 * @param key
	 *            the key used to search. Input parameter.
	 * @exception IndexFullDeleteException
	 *                if no record deleted or failed by any reason
	 * @return RID of the record deleted. Can not return null.
	 */
	RID deleteKey(KeyClass key,Transaction tx,String table) throws Exception {
		KeyDataEntry entry;
		RID rid = new RID();

		entry = getFirst(rid,tx,table);

		if (entry == null) {
			// it is supposed there is at least a record
			throw new IndexFullDeleteException("No records found");
		}
		if (BT.KeyCompare(key, entry.key) < 0) {
			// it is supposed to not smaller than first key
			throw new IndexFullDeleteException("First key is bigger");
		}

		while (BT.KeyCompare(key, entry.key) > 0) {
			entry = getNext(rid,tx,table);
			if (entry == null)
				break;
		}

		if (entry == null)
			rid.slotNo--;
		else if (BT.KeyCompare(key, entry.key) != 0)
			rid.slotNo--; // we want to delete the previous key

		deleteSortedRecord(rid,tx,table);
		return rid;
	}

	/**
	 * This function encapsulates the search routine to search a BTIndexPage by
	 * B++ search algorithm
	 * 
	 * @param key
	 *            the key value used in search algorithm. Input parameter.
	 * @return It returns the page_no of the child to be searched next.
	 * @exception IndexSearchException
	 *                Index search failed;
	 */
	PageID getPageNoByKey(KeyClass key,Transaction tx,String table) throws Exception {
		KeyDataEntry entry;
		int i;

		for (i = getSlotCnt(tx,table) - 1; i >= 0; i--) {
			entry = BT.getEntryFromBytes(getData(), getSlotOffset(i,tx,table),
					getSlotLength(i,tx,table), keyType, NodeType.INDEX,tx,table);

			if (BT.KeyCompare(key, entry.key) >= 0) {
				return ((IndexData) entry.data).getData();
			}
		}
		return getPrevPage(tx,table);

	}

	public KeyDataEntry getFirst(RID rid,Transaction tx,String table) throws Exception {
		KeyDataEntry entry;

		rid.pageNo = getCurPage(tx,table);
		rid.slotNo = 0;

		if (getSlotCnt(tx,table) == 0) {
			return null;
		}

		entry = BT.getEntryFromBytes(getData(), getSlotOffset(0,tx,table),
				getSlotLength(0,tx,table), keyType, NodeType.INDEX,tx,table);
		return entry;
	}

	public KeyDataEntry getNext(RID rid,Transaction tx,String table) throws Exception {
		KeyDataEntry entry;
		int i;
		rid.slotNo++;
		i = rid.slotNo;
		if (rid.slotNo >= getSlotCnt(tx,table)) {
			return null;
		}

		entry = BT.getEntryFromBytes(getData(), getSlotOffset(i,tx,table),
				getSlotLength(i,tx,table), keyType, NodeType.INDEX,tx,table);
		return entry;
	}

	/**
	 * You will recall that the index pages have a left-most pointer that is
	 * followed whenever the search key value is less than the least key value
	 * in the index node. The previous page pointer is used to implement the
	 * left link.
	 * 
	 * @return
	 * @throws IOException
	 */
	public PageID getLeftLink(Transaction tx,String table) throws Exception {
		return getPrevPage(tx,table);
	}

	/**
	 * You will recall that the index pages have a left-most pointer that is
	 * followed whenever the search key value is less than the least key value
	 * in the index node. The previous page pointer is used to implement the
	 * left link. The function sets the left link.
	 * 
	 * @param left
	 *            the PageId of the left link you wish to set. Input parameter.
	 * @exception IOException
	 *                I/O errors
	 */
	protected void setLeftLink(PageID left,Transaction tx,String table) throws Exception {
		setPrevPage(left,tx,table);
	}

	/**
	 * It is used in full delete
	 * 
	 * @param key
	 *            the key is used to search. Input parameter.
	 * @param pageNo
	 *            It returns the pageno of the sibling.
	 * @return 0 if no sibling; -1 if left sibling; 1 if right sibling.
	 * @exception IndexFullDeleteException
	 *                delete failed
	 */

	int getSibling(KeyClass key, PageID pageNo,Transaction tx,String table) throws Exception {
		if (getSlotCnt(tx,table) == 0) {
			return 0;
		}

		int i;
		KeyDataEntry entry;
		for (i = getSlotCnt(tx,table) - 1; i >= 0; i--) {
			entry = BT.getEntryFromBytes(getData(), getSlotOffset(i,tx,table),
					getSlotLength(i,tx,table), keyType, NodeType.INDEX,tx,table);
			if (BT.KeyCompare(key, entry.key) >= 0) {
				if (i != 0) {
					entry = BT.getEntryFromBytes(getData(),
							getSlotOffset(i - 1,tx,table), getSlotLength(i - 1,tx,table),
							keyType, NodeType.INDEX,tx,table);
					pageNo.pageId = ((IndexData) entry.data).getData().pageId;
					return -1; // left sibling
				} else {
					pageNo.pageId = getLeftLink(tx,table).pageId;
					return -1; // left sibling
				}
			}
		}
		entry = BT.getEntryFromBytes(getData(), getSlotOffset(0,tx,table),
				getSlotLength(0,tx,table), keyType, NodeType.INDEX,tx,table);
		pageNo.pageId = ((IndexData) entry.data).getData().pageId;
		return 1; // right sibling
	}

	/**
	 * find the position for old key by findKeyData, where the newKey will be
	 * returned .
	 * 
	 * @newKey It will replace certain key in index page. Input parameter.
	 * @oldKey It helps us to find which key will be replaced by the newKey.
	 *         Input parameter.
	 * @return false if no key was found; true if success.
	 * @exception IndexFullDeleteException
	 *                delete failed
	 */

	boolean adjustKey(KeyClass newKey, KeyClass oldKey,Transaction tx,String table) throws Exception {
		KeyDataEntry entry = findKeyData(oldKey,tx,table);

		if (entry == null)
			return false;

		RID rid = deleteKey(entry.key,tx,table);
		if (rid == null)
			throw new IndexFullDeleteException("Rid is null");

		rid = insertKey(newKey, ((IndexData) entry.data).getData(),tx,table);
		if (rid == null)
			throw new IndexFullDeleteException("Rid is null");

		return true;
	}

	/**
	 * find entry for key by B+ tree algorithm, but entry.key may not equal
	 * KeyDataEntry.key returned.
	 * 
	 * @param key
	 *            input parameter.
	 * @return return that entry if found; otherwise return null;
	 * @exception IndexSearchException
	 *                index search failed
	 * 
	 */
	KeyDataEntry findKeyData(KeyClass key,Transaction tx,String table) throws Exception {
		KeyDataEntry entry;

		for (int i = getSlotCnt(tx,table) - 1; i >= 0; i--) {
			entry = BT.getEntryFromBytes(getData(), getSlotOffset(i,tx,table),
					getSlotLength(i,tx,table), keyType, NodeType.INDEX,tx,table);

			if (BT.KeyCompare(key, entry.key) >= 0) {
				return entry;
			}
		}
		return null;
	}

	/**
	 * find a key by B++ algorithm, but returned key may not equal the key
	 * passed in.
	 * 
	 * @param key
	 *            input parameter.
	 * @return return that key if found; otherwise return null;
	 * @exception IndexSearchException
	 *                index search failed
	 * 
	 */
	KeyClass findKey(KeyClass key,Transaction tx,String table) throws Exception {
		return findKeyData(key,tx,table).key;
	}

	/**
	 * It is used in full delete
	 * 
	 * @param indexPage
	 *            the sibling page of this.
	 * @param parentIndexPage
	 *            the parant of indexPage and this.
	 * @param direction
	 *            -1 if "this" is left sibling of indexPage ; 1 if "this" is
	 *            right sibling of indexPage. Input parameter.
	 * @param deletedKey
	 *            the key which was already deleted, and cause redistribution.
	 *            Input parameter.
	 * @exception RedistributeException
	 *                Redistribution failed
	 * @return true if redistrbution success. false if we can not redistribute
	 *         them.
	 */
	boolean redistribute(IndexPage indexPage, IndexPage parentIndexPage,
			int direction, KeyClass deletedKey,Transaction tx,String table) throws Exception {
		try {
			boolean st;
			if (direction == -1) { // 'this' is the left sibling of indexPage
				if ((getSlotLength(getSlotCnt(tx,table) - 1,tx,table) + availableSpace(tx,table)) > ((MAX_FRAME - DPFIXED) / 2)) {
					// cannot spare a record for its underflow sibling
					return false;
				} else {
					// get its sibling's first record's key
					RID dummyRid = new RID();
					KeyDataEntry firstEntry, lastEntry;
					firstEntry = indexPage.getFirst(dummyRid,tx,table);

					// get the entry pointing to the right sibling

					KeyClass splitKey = parentIndexPage.findKey(firstEntry.key,tx,table);

					// get the leftmost child pointer of the right sibling
					PageID leftMostPageId = indexPage.getLeftLink(tx,table);

					// insert <splitKey,leftMostPageId> to its sibling
					indexPage.insertKey(splitKey, leftMostPageId,tx,table);

					// get the last record of itself
					lastEntry = BT.getEntryFromBytes(getData(),
							getSlotOffset(getSlotCnt(tx,table) - 1,tx,table),
							getSlotLength(getSlotCnt(tx,table) - 1,tx,table), keyType,
							NodeType.INDEX,tx,table);

					// set sibling's leftmostchild to be lastPageId
					indexPage.setLeftLink(((IndexData) (lastEntry.data))
							.getData(),tx,table);

					// delete the last record from the old page
					RID delRid = new RID();
					delRid.pageNo = getCurPage(tx,table);
					delRid.slotNo = getSlotCnt(tx,table) - 1;

					if (deleteSortedRecord(delRid,tx,table) == false)
						throw new RedistributeException("Delete record failed");

					// adjust the entry pointing to sibling in its parent
					if (deletedKey != null) {
						st = parentIndexPage.adjustKey(lastEntry.key,
								deletedKey,tx,table);
					} else {
						st = parentIndexPage.adjustKey(lastEntry.key, splitKey,tx,table);
					}
					if (st == false)
						throw new RedistributeException("adjust key failed");
					return true;
				}
			} else { // 'this' is the right sibling of indexPage
				if ((getSlotLength(0,tx,table) + availableSpace(tx,table)) > ((MAX_FRAME - DPFIXED) / 2)) {
					// cannot spare a record for its underflow sibling
					return false;
				} else {
					// get the first record
					KeyDataEntry firstEntry;
					firstEntry = BT.getEntryFromBytes(getData(),
							getSlotOffset(0,tx,table), getSlotLength(0,tx,table), keyType,
							NodeType.INDEX,tx,table);

					// get its leftmost child pointer
					PageID leftMostPageId = getLeftLink(tx,table);

					// get the entry in its parent pointing to itself
					KeyClass splitKey;
					splitKey = parentIndexPage.findKey(firstEntry.key,tx,table);

					// insert <split, leftMostPageId> to its left sibling

					indexPage.insertKey(splitKey, leftMostPageId,tx,table);

					// set its new leftmostchild
					setLeftLink(((IndexData) (firstEntry.data)).getData(),tx,table);

					// delete the first record
					RID delRid = new RID();
					delRid.pageNo = getCurPage(tx,table);
					delRid.slotNo = 0;
					if (deleteSortedRecord(delRid,tx,table) == false)
						throw new RedistributeException("delete record failed");

					// adjust the entry pointing to itself in its parent
					if (parentIndexPage.adjustKey(firstEntry.key, splitKey,tx,table) == false)
						throw new RedistributeException("adjust key failed");
					return true;
				}
			} // else
		} // try
		catch (Exception e) {
			throw new RedistributeException("redistribute failed");
		}
	}

}
